package org.xqh.study.leetcode.bytedance;


import org.xqh.study.leetcode.algorithm.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName ReverseKGroup
 * @Description K 个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * @Author xuqianghui
 * @Date 2021/2/15 10:39
 * @Version 1.0
 */
public class ReverseKGroup {

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6,
                new ListNode(7, new ListNode(8))))))));
        reverseKGroup22(head, 3);
    }

    /**
     * 使用了外部存储
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode res  = new ListNode(0);
        ListNode tmp = head;
        List<ListNode> list = new ArrayList<>();
        while (tmp != null){
            list.add(tmp);
            tmp = tmp.next;
        }
        int size = (list.size() / k);
        ListNode cur = res;
        for(int i = 0; i < size ; i ++){
            for(int j = k - 1; j >= 0; j --){
                int idx = i * k + j;
                cur.next = list.get(idx);
                cur = cur.next;
            }
        }
        ListNode lastNode = null;
        if(list.size() % k != 0){
            lastNode = list.get(size * k);
        }
        cur.next = lastNode;
        return res.next;
    }

    /**
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup22(ListNode head, int k){
        if(k == 1){
            return head;
        }
        ListNode res = new ListNode(0);
        int i = 0;
        ListNode prev = null, obj = res, cur = head, first = null;
        while (null != cur){
            i ++;
            ListNode ct = new ListNode(cur.val);
            if(i % k == 0){
                first = cur;
                ListNode tmp = obj.next;
                obj.next = ct;
                ct.next = tmp;
                i = 0;
                obj = prev;
            }else {
                if(i % k == 1){
                    prev = ct;
                }
                ListNode tmp = obj.next;
                obj.next = ct;
                ct.next = tmp;
            }

            cur = cur.next;
        }

        if(i != 0){
            obj.next = first.next;
        }

        return res.next;
    }
}
